package com.goudan.practice.tree;

/**
 * 平衡二叉树
 */
public class BalanceTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 返回值信息
     */
    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean i, int h) {
            isBalanced = i;
            height = h;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        System.out.println(process(head).isBalanced);
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(true, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        // x为头的节点的高度：左树和右树较大的那个高度再加上我自己(+1)
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 是否是平衡树：我左树得是平衡，右树得是平衡树，并且我左树和右树的高度差的绝对值得小于2
        boolean isBalanced = true;
        if (!leftInfo.isBalanced) {
            isBalanced = false;
        }
        if (!rightInfo.isBalanced) {
            isBalanced = false;
        }
        if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalanced = false;
        }
        return new Info(isBalanced, height);
    }
}
